#pragma once

#include "Constants.h"
#include <xstring>
using namespace std;

// BinTreeNode structure
// 
typedef struct Node
{
	Node(string name)
	{
		sName = name;
		plChild = NULL;
		prChild = NULL;
	}

	Node* plChild;
	Node* prChild;
	string sName;

} BinTreeNode, * BinTreeNodePtr;

// stack structure
#define STACK_SIZE 100

typedef struct stack
{
	BinTreeNode* node[STACK_SIZE];
	bool tag[STACK_SIZE];
	int top;

	// set default value
	// 
	stack()
	{
		top = -1;
		memset(node, 0, sizeof(BinTreeNode*) * STACK_SIZE);
		memset(node, 0, sizeof(bool) * STACK_SIZE);
	}

	void push(BinTreeNodePtr pNode)
	{
		node[++top] = pNode;
	}

	BinTreeNodePtr pop()
	{
		if (top != -1)
		{
			return node[top--];
		}
		else
		{
			return NULL;
		}
	}
	void changeTag(bool bUnloadable = false)
	{
		tag[top] = bUnloadable;
	}

} seqstack;

/*
BinaryTree's operation class. BinaryTree strcture is not defined in this class.
*/
class DLLEXPIMP BinTreeOp
{
public:
	// ------- Calculate BinTree---------------------------
	// location 
	static BinTreeNode* locateNode(BinTreeNode* pRoot, string name);
	// Calculate BinTree
	static int getNodeCout(BinTreeNode* pRoot);
	// judge tree's equal
	static bool isEqual(BinTreeNode* pTree1, BinTreeNode* pTree2);

	// -------------------Tranverser BinTree-----------------------------
	//--Recursive method--
	static void TLR(BinTreeNodePtr pRoot);// Front
	static void LTR(BinTreeNodePtr pRoot);// Middle
	static void LRT(BinTreeNodePtr pRoot);// Back
	//--Non-recursive methods--
	static void TLR_NoRecursive(BinTreeNode* pRoot);
	static void LTR_NoRecursive(BinTreeNode* pRoot);
	static void LRT_NoRecursive(BinTreeNode* pRoot);
};


